/*
 * @Author: your name
 * @Date: 2021-04-08 15:41:08
 * @LastEditTime: 2021-04-08 17:52:56
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \git\Javascript_\测试\广度优先算法.js
 */
// 深度优先
function DFS(node, nodeList) {
  if (node) {
    nodeList.push(node);
    const children = node.children;
    for (let i = 0; i < children.length; i++) {
      DFS(children[i], nodeList);
    }
  }
  return nodeList;
}

// 深度优先：栈实现
function DFS2(node) {
  let nodes = [];
  if (node) {
    // 存储所有子节点
    let stack = [];
    stack.push(node);
    // 向下遍历
    while (stack.length !== 0) {
      const item = stack.pop();
      nodes.push(item);
      const children = item.children;
      // 同级遍历: 后进先出，所以倒序
      for (let i = children.length - 1; i >= 0; i--) {
        stack.push(children[i]);
      }
    }
  }
  return nodes;
}

// 1. div
// 2. stack=[span1, span0]; stack=[span1]; nodes=[div0, span0]; stack=[span1, div, a]
// 3. stack=[span1, div]; nodes=[span1, a]

// 广度优先：队列实现
function BFS(node) {
  let nodes = [];
  if (node) {
    let queue = [];
    queue.unshift(node);
    while (queue.length !== 0) {
      const item = queue.shift();
      nodes.push(item);
      const children = item.children;
      for (let i = 0; i < children.length; i++) {
        queue.push(children[i]);
      }
    }
  }
  return nodes;
}

// 1. queue=[div]
// 2. queue=[span0, span1];queue=[span1];nodes=[span0];queue=[span1, a, div]
// 3. queue=[a, div];nodes=[span0,span1];;queue=[]

window.onload = function () {
  console.time();
  console.log(DFS2(document.getElementById("root")));
  console.timeEnd();

  console.time();
  console.log(BFS(document.getElementById("root")));
  console.timeEnd();
};
